//
// Created by isabella on 25-6-3.
//
#include <Sort.h>

void HeapSort::heapify(vector<int>& nums) {
    for(int i = nums.size() / 2 - 1; i >= 0; i--) {
        sink(nums,i,nums.size());
    }
}

void HeapSort::sink(vector<int>& nums,int index,int range) {
    if (index >= range/2) {
        return;
    }
    int left=2*index+1;
    int right=2*index+2;
    if(right<range) {
        //有两个子节点
        if(nums[left]>=nums[right]&&nums[index]>nums[right]) {
            int temp=nums[index];
            nums[index]=nums[right];
            nums[right]=temp;
            sink(nums,right,range);
        }else if(nums[left]<nums[right]&&nums[index]>nums[left]) {
            int temp=nums[index];
            nums[index]=nums[left];
            nums[left]=temp;
            sink(nums,left,range);
        }
    }else {
        //只有一个左子节点
        if(nums[index]>nums[left]) {
            int temp=nums[index];
            nums[index]=nums[left];
            nums[left]=temp;
            sink(nums,left,range);
        }
    }
}

vector<int> HeapSort::sort(vector<int> nums) {
    vector<int> result;
    heapify(nums);
    int k=nums.size()-1;
    while(k>=0) {
        result.emplace_back(nums[0]);
        int temp=nums[k];
        nums[k]=nums[0];
        nums[0]=temp;

        sink(nums,0,k);
        k--;
    }
    return result;
}






